package com.frank.leetcode.question_1_5;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
 * 4. 两个排序数组的中位数
 * 难度: 困难
 * <p>
 * Question :
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
 * 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
 * Demo 1:
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 中位数是 2.0
 * Demo 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 中位数是 (2 + 3)/2 = 2.5
 * <p>
 * <p>
 * 中位数
 * 中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。
 * 对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。
 * 如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。
 * Created by zhy on 2018/5/31.
 */
public class FindMedianSortedArrays {
    private static Logger LOG = LoggerFactory.getLogger(FindMedianSortedArrays.class);

    @Test
    public void run() {
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{3,4};

        double val = findMedianSortedArrays(nums1, nums2);
        System.out.println("中位数: " + val);
    }

    /**
     * 分治法 的merge
     */
    private double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        boolean ov;//odd or even
        int index;
        if (length % 2 == 0) {
            //偶数
            ov = true;
            index = length / 2;
        } else {
            ov = false;
            index = (length + 1) / 2;
        }
        System.out.println(ov + " " + index);

        int[] num = new int[index + 1];
        //只有2个值的时候直接交换值
        int j = 0;
        int k = 0;
        for (int i = 0; i < index + 1; i++) {
            if (j < nums1.length && k < nums2.length) {
                if (nums1[j] <= nums2[k]) {
                    num[i] = nums1[j];
                    j++;
                } else {
                    num[i] = nums2[k];
                    k++;
                }
            } else if (j >= nums1.length && k < nums2.length) {
                num[i] = nums2[k];
                k++;
            } else if (k >= nums2.length && j < nums1.length) {
                num[i] = nums1[j];
                j++;
            }
        }

        if (ov) {
            return ((double) (num[index - 1] + num[index])) / 2;
        } else {
            return num[index - 1];
        }
    }
}